package tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class _0711_中序遍历 {



    class Command {
        public TreeNode node;
        public String str;
        public Command(TreeNode node, String str) {
            this.node = node;
            this.str = str;
        }
    }


        public List<Integer> inorderTraversal(TreeNode root) {

            if (root == null) {
                return Collections.emptyList();
            }
            List<Integer> result = new ArrayList<>();
            LinkedList<Command> q = new LinkedList<>();
            q.push(new Command(root,"go"));
            while (!q.isEmpty()) {
                Command pop = q.pop();

                if (pop.str.equals("p")){

                    result.add(pop.node.val);
                }else{
                    TreeNode t = pop.node;
                    if (t.right != null) {
                        q.push(new Command(t.right,"go"));
                    }
                    q.push(new Command(t,"p"));

                    if (t.left != null) {
                        q.push(new Command(t.left,"go"));
                    }
                }
            }
            return result;
        }

}
